/**
 * @class
 */
export default class TreeNode {
    /**
     * @param {*} value
     * @param {TreeNode|null} [left]
     * @param {TreeNode|null} [right]
     * @param {number} [count]
     */
    constructor(value, left = null, right = null,count=1) {
        this.value = value;
        this.left = left;
        this.right = right;
        this.count = count; //相同节点数量，主要是为了二叉搜索树不重复
    }
}

/**
 * 根据给定的数字数组构建一棵二叉搜索树（BST）。
 *
 * 数组中的每个元素将依次插入到 BST 中，遵循左小右大的规则。
 * 如果数组为空，则返回 null。
 *
 * @param {number[]} arr - 用于构建 BST 的数字数组。
 * @returns {TreeNode|null} 返回构建好的二叉搜索树的根节点，如果数组为空则返回 null。
 */
export function buildBinarySearchTree(arr){
    if(arr.length === 0) return null

    let root=new TreeNode(arr[0])
    for(let i=1;i<arr.length;i++){
        addNode(root,arr[i])
    }
    return root
}
/**
 * 添加节点
 * @param node
 * @param value
 * @returns {*|null}
 */
export function addNode(node, value) {
    if (node === null) return new TreeNode(value);

    if (value === node.value) {
        node.count++;
    } else if (value > node.value) {
        node.right = addNode(node.right, value);
    } else {
        node.left = addNode(node.left, value);
    }
    return node;
}

/**
 * 在二叉搜索树（BST）中查找目标值。
 *
 * 如果目标值存在于树中，返回对应的节点；否则返回 false。
 *
 * @param {TreeNode|null} root - BST 的根节点。
 * @param {number} target - 要查找的目标值。
 * @returns {TreeNode|false} 如果找到目标值，返回对应节点；否则返回 false。
 */

export function BinarySearch(root,target){
    if(root===null) return false
    if(root.value===target){
        return root
    }else if(target>root.value){
        return BinarySearch(root.right,target)
    }else{
        return BinarySearch(root.left,target)
    }
}

/**
 * 在二叉搜索树中查找最大值节点。
 * @param {TreeNode|null} tree - BST 的根节点。
 * @returns {TreeNode|null} 返回最大值所在的节点，如果树为空则返回 null。
 */
export function findMax(tree) {
    if (tree === null) return null;
    while (tree.right !== null) {
        tree = tree.right;
    }
    return tree;
}

/**
 * 在二叉搜索树中查找最小值节点。
 * @param {TreeNode|null} tree - BST 的根节点。
 * @returns {TreeNode|null} 返回最小值所在的节点，如果树为空则返回 null。
 */
export function findMin(tree) {
    if (tree === null) return null;
    while (tree.left !== null) {
        tree = tree.left;
    }
    return tree;
}

/**
 * 删除二叉搜索树中的某个目标节点，并返回调整后的树的根节点。
 *
 * @param tree   当前处理的子树（或整个树）的根节点
 * @param target 要删除的节点值
 * @returns {*}  返回删除目标节点后的子树（或整棵树）新的根节点
 */
export function deleteNode(tree, target) {
    if (tree === null) return null; // 如果当前节点为空，说明树为空，直接返回 null

    if (target > tree.value) {
        // 1. 目标值比当前节点值大，说明要去右子树中寻找并删除目标节点

        // 为什么要这样写？这个函数的目的是返回“删除了某个节点之后的树”的根节点。
        // 对于任意节点来说，这个函数会在它的子树中继续查找目标节点并删除，
        // 最后返回处理过的子树的根节点。所以我们要把处理后的右子树重新挂回当前节点。
        tree.right = deleteNode(tree.right, target);
        return tree;

    } else if (target < tree.value) {
        // 2. 目标值比当前节点值小，说明目标节点位于左子树

        // 同样，我们要在左子树上递归执行删除操作，并将返回结果挂回当前节点的左子树
        tree.left = deleteNode(tree.left, target);
        return tree;

    } else {
        // 3. 找到了要删除的目标节点，下面分情况处理：

        // 3.1 当前节点是叶子节点（没有左子树和右子树），可以直接删除
        if (tree.left === null && tree.right === null) {
            return null;
        }

        // 3.2 当前节点只有右子树（无左子树）
        else if (tree.left === null && tree.right !== null) {
            return tree.right; // 返回右子树作为新的子树根节点
        }

        // 3.3 当前节点只有左子树（无右子树）
        else if (tree.left !== null && tree.right === null) {
            return tree.left; // 返回左子树作为新的子树根节点
        }

        // 3.4 当前节点有左右两个子树
        else {
            // 要删除当前节点，又不能直接删除（因为有两个子节点），
            // 所以需要用一个“合适”的节点替代当前节点，以维持 BST 的性质。
            // 一种常见做法是：从左子树中找到最大值节点（也可以用右子树的最小值），
            // 因为它是小于当前节点但最大的数，用来替代当前节点再合适不过。

            let node = findMax(tree.left);           // 找到左子树中的最大节点
            tree.value = node.value;                 // 用该最大节点的值替代当前节点的值

            // 然后从左子树中递归删除这个最大节点，注意要将返回值重新赋给 tree.left
            tree.left = deleteNode(tree.left, node.value);

            return tree;
        }
    }
}

/**
 * 查找某个节点在中序遍历中的前驱节点
 * @param root
 * @param target
 * @returns {null|TreeNode}
 */
export function findPreNode(root,target){
    if(root===null) return null
    let current=root
    let preNode=null
    while(current!==null){ //说明没找到
        //1.target在右边，则current有可能是前驱节点,继续往右搜索
        // 下面去找左子树中最大节点，有可能左子树为空
        if(target>current.value){
            preNode=current
            current=current.right
        }
        //2. target在左边，当前节点不可能是前驱节点（中序的特点）, 继续往左
        else if(target<current.value){
            current=current.left
        }
        //3. 找到目标节点,前驱节点比目标节点小，但是是目标节点前面一个，因此一定是目标节点右子树中最大的,
        // 右子树可能为空，根据中序特点，前驱就是当前节点的上一个节点
        else{
            if(current.left!==null){
                preNode=findMax(current.left)
            }

            //可以提前退出了
            break
        }
    }
    return preNode
}


/**
 * 查找中序遍历中的后驱节点
 * @param root
 * @param target
 * @returns {null}
 */
export function findNextNode(root,target){
    if(root===null) return null
    let current=root
    let nextNode=null
    while(current!==null){ //说明没找到
        //1.节点值小于目标值，不可能是后驱节点
        if(target>current.value){
            current=current.right
        }
        //2. 节点值大于目标值，有可能是后驱节点
        else if(target<current.value){
            nextNode=current
            current=current.left
        }
        //3. 找到目标节点,后驱节点是大于目标节点的值中最小的
        else{
            if(current.right!==null){
                //如果有右子树
                nextNode=findMin(current.right)
            }
            //可以提前退出了
            break
        }
    }
    return nextNode
}